package com.codingvip.sort;

public class SplitSort {
    private int num = 0;

    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n - 1);
        return num;
    }

    private void mergeSortCounting(int[] a, int p, int r) {
        System.out.println("");

        System.out.print("P=" + p + ",r=" + r);
        if (p >= r) {
            return;
        }
        int q = (p + r) / 2;
        System.out.print(",q="+q);
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q + 1, r);
        merge(a, p, q, r);


    }

    private void merge(int[] a, int p, int q, int r) {
        System.out.println("Merge::");
        System.out.print("P=" + p + ",Q=" + q+",R="+r);
        int i = p, j = q + 1, k = 0;
        int[] tmp = new int[r - p + 1];
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                num += q - i + 1;
                tmp[k++] = a[j++];
            }
        }
        while (i <= q) {
            tmp[k++] = a[i++];
        }
        while (j <= r) {
            tmp[k++] = a[j++];
        }
        //从tmp 中拷回A

        for (i = 0; i <= r - p; ++i) {
            a[p + i] = tmp[i];
        }
    }
}
